package unit13_动态规划.part3_大厂冲刺题;

public class IsMatch {
    public boolean isMatch(String ss1, String ss2) {
        char[] s1 = ss1.toCharArray();
        char[] s2 = ss2.toCharArray();
        int m = s1.length;
        int n = s2.length;
        int i, j;
        boolean[][] f = new boolean[m + 1][n + 1];
        for (i = 0; i <= m; i++) {
            f[i][0] = (i == 0);
            for (j = 1; j <= n; j++) {
                f[i][j] = false;
                if (s2[j - 1] != '*') {
                    if (i > 0 && (s2[j - 1] == '.' || s2[j - 1] == s1[i - 1])) {
                        f[i][j] |= f[i - 1][j - 1];
                    }
                } else {
                    if (j - 2 >= 0) {
                        f[i][j] |= f[i][j - 2];
                    }
                    if (i > 0 && j - 2 >= 0 && (s2[j - 2] == '.' || s2[j - 2] == s1[i - 1])) {
                        f[i][j] |= f[i - 1][j];
                    }
                }

            }
        }
        return f[m][n];
    }
}
